public class MyLinkList {
    //双向链表的模拟实现；
    static class Node{
        public int val;
        public Node prev;
        public Node next;
        public Node (int val){
            this.val=val;
        }
    }
    //头节点；
    public Node head;
    //尾结点；
    public Node last;
    //1.进行打印该双向链表；
    public void disPlay(){
        Node cur=head;
        while(cur!=null){
            System.out.print(cur.val+"  ");
            cur=cur.next;
        }
        System.out.println();
    }
    //2.进行获取双向链表的长度；
    public int size(){
        int count=0;
        Node cur=head;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    //3，进行向双向链表进行插入头节点；
    public void addFirstNode(int date){
        Node newNode=new Node(date);
        if(head==null){
            head=newNode;
            last=newNode;
        }else{
            newNode.next=head;
            head.prev=newNode;
            head=newNode;
        }
    }
    //4.进行向双向链表中进行尾插法；
    public void addLastNode(int date){
        Node newNode =new Node(date);
        if(head==null){
            head=newNode;
            last=newNode;
        }else{
            newNode.prev=last;
            last.next=newNode;
            last=newNode;
        }
    }
    //5.进行向双向链表中的任意位置中插入不同的节点；
    public void insertNode(int index,int key){
        int len=size();
        //首先进行判断插入位置的合法性；
        while(index<0||index>len){
            System.out.println("插入节点的位置不合法.....");
            return;
        }
        //如果插入的位置是头节点；
        if(index==0){
            addFirstNode(key);
        }
        //如果插入的位置是尾结点；
        if(index==len){
            addLastNode(key);
        }
        //如果插入的位置是中间位置；
        Node cur=serchMiddleNode(index);
        Node newNode=new Node(key);
        newNode.next=cur;
        cur.prev.next=newNode;
        newNode.prev=cur.prev;
        cur.prev=newNode;
    }
    //6.给定值进行寻找中间位置的节点；
    public Node serchMiddleNode(int index){
        Node cur=head;
        while(index!=0){
            cur=cur.next;
            index--;
        }
        return cur;
    }
    //7.进行删除要删除节点的第一个值；
    public void removeFirst(int toFind){
        Node cur=head;
        while(cur!=null){
            if(cur.val==toFind){
                if(cur==head){
                    head=head.next;
                    if(head.next==null){
                        //执行到此处说明该双向链表只有一个节点；
                        last=null;
                    }else{
                        head.prev=null;
                    }
                }else{
                    //进行考虑中间和尾巴位置的情况；
                    //程序执行到此处说明要删除节点的位置是尾巴位置；
                    if(cur.next==null){
                        cur.prev.next=cur.next;
                        last=last.prev;
                    }else{
                        //程序执行到此处说明要删除的节点是在中间位置；
                        cur.prev.next=cur.next;
                        cur.next.prev=cur.prev;
                    }
                }
                return;
            }
            cur=cur.next;
        }
    }
    //8，进行判断双向链表中是否含有某个节点；
    public boolean contains(int key){
        Node cur=head;
        while(cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //9.进行删除双向链表中所以要删除的节点；
    public void removeAllNode(int removeKey){
        Node cur=head;
        while(cur!=null){
            if(cur.val==removeKey){
                if(cur==head){
                    if(head.next==null){
                        last=null;
                    }else{
                        head.prev=null;
                    }
                }else{
                    if(cur.next==null){
                        cur.prev.next=cur.next;
                        last=last.prev;
                    }else{
                        cur.prev.next=cur.next;
                        cur.next.prev=cur.prev;
                    }
                }
            }
            cur=cur.next;
        }
    }


}
